#include <iostream>
#include <vector>
#include <string>

using namespace std;
using ll = long long;
long long f(string& s1, string& s2)
{
    int n =s1.size(), m = s2.size(), ret = 0;
    vector<int> nums;
    auto Find = [&](int i)->int 
    {
        int left = i, right = nums.size() - 1;
        while(left < right)
        {
            int mid = (left + right + 1) >> 1;
            if(nums[mid] < nums[i] + m) left = mid;
            else right = mid - 1;
        }
        return left;
    };
    for(int i = 0; i + m - 1 < n; i++)
    {
        int j = 0;
        while(j < m && s2[j] == s1[i + j]) j++;
        if(j == m) nums.push_back(i);
    }
    for(int i = 0; i < nums.size(); i++)
    {
        ret++;
        // cout << i << "->";
        i = Find(i);      
        // cout << i << endl;  
    }
    return ret;
}

int main()
{
    int n; cin >> n;
    int a;
    string s1, s2;
    while(n--)
    {
        cin >>a >>a;
        cin >> s1 >> s2;
        cout << f(s1, s2)<<endl;
    }
    return 0;
}